package leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangmaolin1
 * @date 2023/11/11 10:19
 */
public class _105 {
    private Map<Integer, Integer> inOrderVal2IndexMap = new HashMap<>();

    /**
     * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
     * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
     * 输出: [3,9,20,null,null,15,7]
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        for (int i = 0; i < inorder.length; i++) {
            inOrderVal2IndexMap.put(inorder[i], i);
        }
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    /**
     * 1. 找到根节点，构造根节点
     * 2. 找到左子树范围，构造左子树
     * 3. 找到右子树范围，构造右子树
     * preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
     * 1. 先：根：3，左：9，右：20-7
     * 2. 中：根：3，左：9，右：15-7
     */
    public TreeNode build(int[] preOrder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart>preEnd || preEnd>=preOrder.length || inStart>inEnd || inEnd>=inorder.length){
            return null;
        }
        int rootVal = preOrder[preStart];
        TreeNode root = new TreeNode(rootVal);
        // 从中序遍历找根节点索引
        Integer rootIndex = inOrderVal2IndexMap.get(rootVal);
       // 确认左子树节点数量，确认先序遍历的左子树范围
        int leftTreeNodeNum = rootIndex-inStart;
        root.left=build(preOrder,preStart+1,preStart+leftTreeNodeNum,inorder,inStart,rootIndex-1);
        root.right =build(preOrder,preStart+leftTreeNodeNum+1,preEnd,inorder,rootIndex+1,inEnd);
        return root;

    }
}
